Xiaoni DU Ji ZHANG Chenhuang WU
We determine the linear complexity of binary sequences derived from the polynomial quotient modulo p defined by $F(u)equiv rac{f(u)-f_p(u)}{p} ~(mod~ p), qquad 0 le F(u) le p-1,~uge 0,$ where fp(u)≡f(u) (mod p), for general polynomials $f(x)in mathbb{Z}[x]$. The linear complexity equals to one of the following values {p2-p,p2-p+1,p2-1,p2} if 2 is a primitive root modulo p2, depending on p≡1 or 3 modulo 4 and the number of solutions of f'(u)≡0 (mod) p, where f'(x) is the derivative of f(x). Furthermore, we extend the constructions to d-ary sequences for prime d|(p-1) and d being a primitive root modulo p2.
In this paper, one new class of quaternary generalized cyclotomic sequences with the period 2pq over F4 is established. The linear complexity of proposed sequences with the period 2pq is determined. The results show that such sequences have high linear complexity.
Chun-e ZHAO Wenping MA Tongjiang YAN Yuhua SUN
Binary sequences with low autocorrelation have important applications in communication systems and cryptography. In this paper, the autocorrelation values of binary Whiteman generalized cyclotomic sequences of order six and period pq are discussed. Our result shows that the autocorrelation of these sequences is four-valued and that the corresponding values are in {-1,3,-5,pq} if the parameters are chosen carefully.
This paper contributes to k-error linear complexity of some generalized cyclotomic binary sequences of length 2pm and pm constructed in recent years. By defining related reference sequences, we find that these sequences possess very low k-error linear complexity for some certain values of the parameter k even though they have high linear complexity. Moreover, we point out that (p-1)-tuple distributions of all these sequences are not span. Thus they should be selected carefully for use in stream cipher systems.
Yuhua SUN Tongjiang YAN Hui LI
Binary sequences with good autocorrelation and large linear complexity have found many applications in communication systems. A construction of almost difference sets was given by Cai and Ding in 2009. Many classes of binary sequences with three-level autocorrelation could be obtained by this construction and the linear complexity of two classes of binary sequences from the construction have been determined by Wang in 2010. Inspired by the analysis of Wang, we deternime the linear complexity and the minimal polynomials of another class of binary sequences, i.e., the class based on the WG difference set, from the construction by Cai and Ding. Furthermore, a generalized version of the construction by Cai and Ding is also presented.
Xiaoping LI Wenping MA Tongjiang YAN Xubo ZHAO
In this letter, we first introduce a new generalized cyclotomic sequence of order two of length pq, then we calculate its linear complexity and minimal polynomial. Our results show that this sequence possesses both high linear complexity and optimal balance on 1 s and 0 s, which may be attractive for use in stream cipher cryptosystems.
Lu ZHAO Qiao-yan WEN Jie ZHANG
The linear complexity of quaternary sequences plays an important role in cryptology. In this paper, the minimal polynomial of a class of quaternary sequences with low autocorrelation constructed by generalized cyclotomic sequences pairs is determined, and the linear complexity of the sequences is also obtained.
We proposed a method for constructing constant-weight and multi-valued sequences from the cyclic difference sets by generalization of the method in binary case proposed by N. Li, X. Zeng and L. Hu in 2008. In this paper we give some properties about sets of such sequences and it is shown that a set of non-constant-weight sequences over Z4 with length 13 from the (13,4,1)-cyclic difference set, and a set of constant-weight sequences over Z5 with length 21 from the (21,5,1)-cyclic difference set have almost highest linear complexities and good profiles of all sequences' linear complexities. Moreover we investigate the value distribution, the linear complexity and correlation properties of a set of sequences with length 57 over GF(8) from the (57,8,1)-cyclic difference set. It is pointed out that this set also has good value distributions and almost highest linear complexities in similar to previous two sets over Z4 with length 13 and Z5 with length 21.
Xiaoping LI Wenping MA Tongjiang YAN Xubo ZHAO
In this letter we propose a new Whiteman generalized cyclotomic sequence of order 4. Meanwhile, we determine its linear complexity and minimal polynomial. The results show that this sequence possesses both high linear complexity and optimal balance on 1 s and 0 s, which may be attractive for cryptographic applications.
Linear complexity profile and correlation measure of order k are important pseudorandomness measures for sequences used in cryptography. We study both measures for a class of binary sequences called Legendre-Sidelnikov sequences. The proofs involve character sums.
Zhihua NIU Zhe LI Zhixiong CHEN Tongjiang YAN
The linear complexity and its stability of periodic sequences are of fundamental importance as measure indexes on the security of stream ciphers and the k-error linear complexity reveals the stability of the linear complexity properly. Recently, Zhou designed an algorithm for computing the k-error linear complexity of 2pn periodic sequences over GF(q). In this paper, we develop a genetic algorithm to confirm that one can't get the real k-error linear complexity for some sequenes by the Zhou's algorithm. Analysis indicates that the Zhou's algorithm is unreasonable in some steps. The corrected algorithm is presented. Such algorithm will increase the amount of computation, but is necessary to get the real k-error linear complexity. Here p and q are odd prime, and q is a primitive root (mod p2).
Chenhuang WU Zhixiong CHEN Xiaoni DU
We define a family of 2e+1-periodic binary threshold sequences and a family of p2-periodic binary threshold sequences by using Carmichael quotients modulo 2e (e > 2) and 2p (p is an odd prime), respectively. These are extensions of the construction derived from Fermat quotients modulo an odd prime in our earlier work. We determine exact values of the linear complexity, which are larger than half of the period. For cryptographic purpose, the linear complexities of the sequences in this letter are of desired values.
Huijuan WANG Qiaoyan WEN Jie ZHANG
This paper studies the 2-adic complexity of the self-shrinking sequence under the relationship between 2-adic integers and binary sequences. Based on the linear complexity and the number of the sequences which have the same connection integer, we conclude that the 2-adic complexity of the self-shrinking sequence constructed by a binary m-sequence of order n has a lower bound 2n-2-1. Furthermore, it is shown that its 2-adic complexity has a bigger lower bound under some circumstances.
Pinhui KE Zheng YANG Jie ZHANG
We determine the autocorrelations of the quaternary sequence over F4 and its modified version introduced by Du et al. [X.N. Du et al., Linear complexity of quaternary sequences generated using generalized cyclotomic classes modulo 2p, IEICE Trans. Fundamentals, vol.E94-A, no.5, pp.1214–1217, 2011]. Furthermore, we reveal a drawback in the paper aforementioned and remark that the proof in the paper by Kim et al. can be simplified.
In this letter, we determine the linear complexity and minimum polynomial of the frequency hopping sequences over GF(q) introduced by Chung and Yang, where q is an odd prime. The results of this letter show that these sequences are quite good from the linear complexity viewpoint. By modifying these sequences, another class of frequency hopping sequences are obtained. The modified sequences also have low Hamming autocorrelation and large linear complexity.
Let p be an odd prime number. We define a family of quaternary sequences of period 2p using generalized cyclotomic classes over the residue class ring modulo 2p. We compute exact values of the linear complexity, which are larger than half of the period. Such sequences are 'good' enough from the viewpoint of linear complexity.
Some new generalized cyclotomic sequences defined by C. Ding and T. Helleseth are proven to exhibit a number of good randomness properties. In this paper, we determine the defining pairs of these sequences of length pm (p prime, m ≥ 2) with order two, then from which we obtain their trace representation. Thus their linear complexity can be derived using Key's method.
In this letter, we generalize the binary sequence introduced by Li et al. in [S. Q. Li et al., On the randomness generalized cyclotomic sequences of order two and length pq, IEICE Trans. Fund, vol. E90-A, no.9, pp.2037-2041, 2007] to sequence over arbitrary prime fields. Furthermore, the auto-correlation distribution and linear complexity of the proposed sequence are presented.
Seok-Yong JIN Young-Joon KIM Hong-Yeop SONG
In this paper, we calculate autocorrelation of new generalized cyclotomic sequences of period pn for any n > 0, where p is an odd prime number.
Jingwei ZHANG Chang-An ZHAO Xiao MA
In this paper, we compare two generalized cyclotomic binary sequences with length 2p2 in terms of the linear complexity. One classical sequence is defined using the method introduced by Ding and Helleseth, while the other modified sequence is defined in a slightly different manner. We show that the modified sequence has linear complexity of 2p2, which is higher than that of the classical one.